A variety of media are used to store digital data such as music content and video data. Examples include magnetic disks, optical discs, and magneto-optical disks. Among such recording media, memory cards that use semiconductor memories including flash ROMs as their recording elements are compact, and thus have become rapidly widespread mainly in compact portable devices, such as movie or digital still cameras and mobile telephone terminals. In particular, semiconductor memories, which have conventionally been used as removable media like memory cards, have recently found application as built-in memories. For example, semiconductor memories, such as flash ROMs, are built in devices and used in place of hard disks.
A memory card and a built-in memory mainly use a semiconductor device called a NAND-type flash memory, which is a recording element on which recorded data can be erased and new data can be recorded. Like a conventional hard disk, the NAND-type flash memory can be used to form an information recording apparatus that is rewritable a plurality of number of times.
A conventional way to manage data stored in a memory card or a built-in memory uses a file system. Data managed using a file system can be shared as files between a plurality of devices that can interpret the same file system. Such file system management enables a user to easily refer to or copy his or her stored data on a plurality of devices.
A file system that has conventionally achieved most widespread use is a file allocation table (FAT) file system. The FAT file system manages areas in a unified manner using a file allocation table (FAT). With its simple structure and easy implementation, the FAT file system is used in many recording media, such as flexible disks, hard disks of personal computers, and memory cards.
FIG. 2 shows the structure of the FAT file system. The FAT file system can be of one of a plurality of types: FAT12, FAT16, and FAT32, which differ from one another in the bit width of the management unit used in their file allocation table. The FAT file system of any of these types uses substantially the same method for managing areas using the file allocation table. In this example, the FAT16 file system will be described.
As shown in FIG. 2, at the beginning of the logical address space is a file system management information area 201, which stores management information for the file system, such as information indicating the unit of area allocation and the size of areas that are managed by the file system.
The file system management information area 201 stores a plurality of sets of management information: a master boot record (MBR) partition table 203, a partition boot sector 204, FATs (205 and 206), and a root directory entry 207, each of which stores information required to manage a user data area 202.
The MBR partition table 203 stores information used to manage areas of the logical address space managed by the file system by dividing the logical address space into a plurality of areas called partitions.
The partition boot sector 204 stores information about management within each partition, such as information about the unit of area management within the partition. The FATs (205 and 206) each store information about the storage position of file data. The FAT file system usually has two FATs (205 and 206) each storing the same information. Even if one FAT (205 or 206) is corrupted, the duplicated FATs of the FAT file system enables access to files by using the other FAT (205 or 206).
The root directory entry 207 stores information about files and directories (directory entries) that are immediately below the root directory.
The FAT file system further includes the user data area 202, which is preceded by the file system management information area 201. The user data area 202 stores main data stored in files and the like. The user data area 202 is managed in units of divisional areas called clusters, which each have a size of 512 bytes to tens of kilobytes. Each cluster stores data stored in files. A file storing a large amount of data uses a plurality of clusters to store the data. The FATs (205 and 206) store link information that is used to manage links between such clusters. Also, a part of the user data area 202 is used to store information about files and sub-directories (directory entries) immediately below the root directory.
FIG. 3 shows the structure of a directory entry of the FAT16 file system.
A directory entry 208, which has 32 bytes, is allocated to each file or each directory, and stores information associated with the file or the directory. More specifically, information representing the 32-byte directory entry 208 is newly created every time when a file or a directory is added, and is stored into the area of the root directory entry 207 or into the user data area 202.
The first eight-byte part of the directory entry 208 stores a file name or a directory name. The following three-byte part stores an extension. The following one-byte part stores attribute information, such as a flag indicating a type either being a file or a directory, and a flag indicating whether the file or the directory is read-only. The following parts may further store information about the last update time and date of the file or the directory, a first cluster number indicating the position of a first cluster among a plurality of clusters storing the file data or the directory data, and a file size indicating the number of bytes of the file.
As described above, the directory entry 208 only stores information indicating the position of the first single cluster storing the file data or the directory data. The positions of data stored in the second and subsequent clusters are managed by the FATs (205 and 206) when the file data or the directory data is larger than the size of one cluster.
FIG. 4 shows the structure of the FAT (205, 206) used in the FAT16 file system.
In the FAT16 file system, the FAT (205, 206) manages 2-byte (16-bit) information as a single FAT entry. A single FAT entry indicates the status of its corresponding single cluster. More specifically, when the user data area 202 includes M clusters, the FAT includes M FAT entries. In this case, the FAT (205, 206) has a size of about 2*M bytes. The first two FAT entries of the FAT store, as a signature, fixed values (0xF8FF, 0xFFFF) indicating the beginning of the FAT. The fourth and fifth bytes of the FAT (205, 206) store an FAT entry corresponding to the first cluster included in the user data area 202. When the four-byte signature stored at the beginning of the FAT is assumed to be the 0-th and 1st FAT entries, the fourth and fifth bytes are the two bytes storing the second FAT entry. As a result, a cluster number of 2 is assigned to the first cluster included in the user data area 202. No clusters with cluster numbers of 0 and 1 exist.
Each FAT entry further indicates the status of the corresponding cluster (occupied, unoccupied, or defective) and a cluster number of a linked cluster. In FIG. 4, for example, an FAT entry with an assigned cluster number of 2 is set as 0x0003 (“3” when expressed as a decimal number), indicating that data subsequent to the data stored in the cluster with the cluster number of 2 is stored in a cluster with a cluster number of 3. In the same manner, an FAT entry with an assigned cluster number of 3 is set as 0x0004 (“4” when expressed as a decimal number), indicating that data subsequent to the data stored in the cluster with the cluster number of 3 is stored in a cluster with a cluster number of 4. An FAT entry with an assigned cluster number of 6 is set as 0xFFFF, indicating that no cluster is linked to this cluster, and this cluster is the end of the link. In the example shown in FIG. 4, the file data is stored over a plurality of clusters in the order of the cluster numbers of 2, 3, 4, 5, and 6. Also, an FAT entry with an assigned cluster number of 7 is set as 0x0000, indicating that the corresponding cluster is not used and is in an unoccupied status. An FAT entry with an assigned cluster number of (M+1) is set as 0xFFF7, indicating that the corresponding cluster is in a defective status, or that the corresponding cluster is for example physically broken and data cannot be recorded into this cluster.
To sum up, the three FAT entry values 0x0000, 0xFFFF, and 0xFFF7 have different special meanings. The FAT entry values from 0x0002 to 0xFFF6 are used as cluster numbers of linked clusters. The other values, that is, the values 0x0001 and 0xFFF8 to 0xFFFE, are reserved and are not used normally.
As described above, the FAT (205, 206) not only manages information about links between areas storing the file data but also manages the use status of each cluster. The available storage space in areas managed using the file system can thus be calculated by referring to the FAT (205, 206) and counting the number of unoccupied clusters. The available storage space calculation process will now be described with reference to FIG. 5.
Available Storage Space Calculation Process
S501:
The access module initializes a variable (FREE_SPACE) indicating the available storage space to zero.
S502:
The access module sets, as a current reference position, the position of an FAT entry with the cluster number of 2 included in the FAT (205, 206), which is read into a RAM of the access module. The present example assumes that the FAT (205, 206) is read in advance from an information recording module into the RAM of the access module.
S503:
The access module determines whether the current reference position setting has reached the end of the FAT to complete the searching for an available storage space throughout the entire FAT. When the searching has been completed, a current value of the variable FREE SPACE is transmitted, as an available storage space, to an application control unit of the access module. The access module then terminates the processing. When the searching has yet to be completed, the access module advances to the processing in step S504.
S504:
The access module determines whether the FAT entry at the current reference position corresponds to an unoccupied cluster.
More specifically, the access module determines that the FAT entry corresponds to an unoccupied cluster when the FAT entry value is 0X0000, and determines that the FAT entry does not correspond to an unoccupied cluster in any other cases.
When determining that the FAT entry corresponds to an unoccupied cluster, the access module advances to the processing in step S505. When determining that the FAT entry does not correspond to an unoccupied cluster, the access module advances to the processing in step S506.
S505:
The access module, which has detected an unoccupied cluster, adds 1 to the value of the variable FREE_SPACE (increments the value by +1).
S506:
The access module advances the current reference position by one FAT entry, and returns to the processing in step S503.
When, for example, the FAT (205, 206) has the structure shown in FIG. 6, the FAT includes 16 unoccupied clusters in total between the FAT entry to which the cluster number of 2 is assigned and the FAT entry to which the cluster number of 31 is assigned. The total number of unoccupied clusters, which is 16 in this case, is transmitted to the application control unit of the access module as the available storage space.
In the available storage space calculation process, the number of unoccupied clusters in the FAT needs to be counted using the values of all FAT entries included in the FAT. The number of FAT entries increases as the total storage space managed using the file system increases. As the number of FAT entries increases, the time required by the available storage space calculation process would increase accordingly.
To solve the above problem, one conventional method uses information about the available storage space prestored in the file system management information area, such as the partition boot sector 204 (see, for example, Patent Citation 1). With this method, the information about the available storage space can be read from the file system management information area 201 to eliminate the available storage space calculation process, which would otherwise be required to be performed by referring to the FAT (205, 206). This method may shorten the time required by the initialization process of the file system including the available storage space calculation process.
Patent Citation 1: Japanese Unexamined Patent Publication No. 2007-214786